package 双指针.二分查找;

/**
 * 解题思路：
 * 这个题可以用二分法来做。值得注意的是要考虑四种情况，且题目有时间复杂度和空间复杂度的要求。
 * <p>
 * 情况1：中间元素的同一元素在右边，且目标元素在右边
 * 情况2：中间元素的同一元素在右边，且目标元素在左边
 * 情况3：中间元素的同一元素在左边，且目标元素在左边
 * 情况4：中间元素的同一元素在左边，且目标元素在右边
 * <p>
 * 注意的点：
 * ①进行判断目标元素的在左边还是右边的核心思想是，除去了mid的相同元素，数组个数是偶数，则没有目标元素，反之，有目标元素
 * ②本来按常人思维，mid同一元素在右边就去判断右边的数组，在左边就去判断左边的数组，但是因为题目的时间复杂度要求，我们
 * 统一判断右边的数组个数。用(right - mid) % 2 == 0。
 * ③本来判断是否存在目标元素是根据“除去了mid的相同元素，再看右边数组个数”，但是具体不好实现，所以分两种情况。
 * 1）、中间元素的同一元素在右边：此时(right - mid) % 2 == 0，证明目标元素存在右边
 * 2）、中间元素的同一元素在左边：此时(right - mid) % 2 ！= 0，证明目标元素在右边
 * ④注意mid和flag的定义都要放到while循环里面，不然会超时
 */
public class 有序数组中的单一元素_540 {

    public static void main(String[] args) {
        System.out.println(1+(5-1)/2);
    }

    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;


        while (left < right) {
            int mid = left + (right - left) / 2;//其实mid就等于(l+r)/2，这里这么写是为了防止溢出
            boolean flag = (right - mid) % 2 == 0;
            if (nums[mid] == nums[mid + 1]) {
                if (flag) {//①mid相同元素在mid右边，且去除该相同元素后，右边数组为奇数。即目标值在右边部分
                    left = mid + 2;
                } else {//②mid相同元素在mid右边，且去除该相同元素后，右边数组为偶数。即目标值在左边部分
                    right = mid - 1;
                }

            } else if (nums[mid] == nums[mid - 1]) {
                if (flag) {//③mid相同元素在mid左边，且去除该相同元素后，左边数组为奇数。即目标值在左边部分
                    /*本来if的条件应该是(mid - left) % 2 != 0，但是由于这样会导致超时，所以我们只用一个变量，flag。
                      即flag为true的时候证明右子块没有目标元素  */
                    right = mid - 2;
                } else {//④mid相同元素在mid左边，且去除该相同元素后，左边数组为偶数。即目标值在右边部分
                    left = mid + 1;
                }

            } else {//如果上面条件都不满足，证明中间的元素就是目标元素
                return nums[mid];
            }

        }
        return nums[left];//这是为了防止数组只有一个元素，那么就直接返回该元素，nums[0]
    }


}
